package com.conjane.algo.binary_search_tree;

import com.conjane.algo.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 实现BinaryTreeInfo接口，主要是能够二叉搜索树能够以树状的形式打印出来
 * @param <E>
 */
public class BinarySearchTree<E> implements BinaryTreeInfo {

    private int size;

    private Node<E> rootNode;

    private Comparator<E> comparator;

    public BinarySearchTree() {
    }

    BinarySearchTree(Comparator comparator) {
        this.comparator = comparator;
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {

    }

    /**
     * 二叉树添加数据
     * @param element 添加元素
     */
    public void add(E element) {
        elementNotNullCheck(element);
        if (rootNode == null) {
            rootNode = new Node<>(element,null);
            size++;
            return;
        }
        // 遍历时父节点
        Node<E> parentNode = rootNode;
        // 遍历时临时节点
        Node<E> tempNode = rootNode;
        int compareResult = 0;
        while (tempNode != null) {
            compareResult = compare(element, tempNode.element);
            parentNode = tempNode;
            if (compareResult > 0) {
                tempNode = tempNode.rightNode;
            } else if (compareResult < 0) {
                tempNode = tempNode.leftNode;
            } else {
                // 新值覆盖旧值
                tempNode.element = element;
            }
        }
        Node<E> node = new Node<>(element,parentNode);
        if (compareResult > 0) {
            parentNode.rightNode = node;
        }
        if (compareResult < 0) {
            parentNode.leftNode = node;
        }
        size++;
    }

    public void remove(E element) {

    }

    public boolean contains(E element) {
        return false;
    }

    public void preOrder(){
        preOrder(this.rootNode);
    }

    public void preOrderWithStack(){
        preOrderWithStack(this.rootNode);
    }
    // 前序遍历：根 左 右
    private void preOrder(Node<E> rootNode) {
        if (rootNode == null) return;
        System.out.print(rootNode.element + " ");
        preOrder(rootNode.leftNode);
        preOrder(rootNode.rightNode);
    }

    /**
     * 以栈方式前序遍历二叉树
     * @param rootNode
     */
    private void preOrderWithStack(Node<E> rootNode){
        if (rootNode == null) return;
        Stack<Node> stack = new Stack<>();
        stack.push(rootNode);
        while (!stack.isEmpty()){
            Node node = stack.pop();
            System.out.print(node.element + " ");
            if (node.rightNode != null){
                stack.push(node.rightNode);
            }
            if (node.leftNode != null){
                stack.push(node.leftNode);
            }
        }
    }

    public void preOrder(Visitor visitor){
        preOrder(this.rootNode,visitor);
    }
    // 带有遍历方式的前序遍历
    private void preOrder(Node<E> rootNode, Visitor visitor) {
        visitor.visit(rootNode.element);
        preOrder(rootNode.leftNode, visitor);
        preOrder(rootNode.rightNode, visitor);
    }

    public void inOrder(){
        inOrder(this.rootNode);
    }

    public void inOrderWithStack(){
        inOrderWithStack(this.rootNode);
    }
    // 中序遍历：左 根 右
    private void inOrder(Node<E> rootNode) {
        if (rootNode == null) return;
        inOrder(rootNode.leftNode);
        System.out.print(rootNode.element + " ");
        inOrder(rootNode.rightNode);
    }

    private void inOrderWithStack(Node<E> rootNode){
        if (rootNode == null) return;
        Stack<Node> stack = new Stack<>();
        Node tempNode = rootNode;
        while (!stack.isEmpty() || tempNode != null){
            while (tempNode != null){
                stack.push(tempNode);
                tempNode = tempNode.leftNode;
            }
            Node popNode = stack.pop();
            System.out.print(popNode.element + " ");
            tempNode = popNode.rightNode;
        }
    }

    public void inOrder(Visitor visitor){
        inOrder(this.rootNode,visitor);
    }
    // 带有遍历方式的中序遍历
    private void inOrder(Node<E> rootNode, Visitor<E> visitor) {
        preOrder(rootNode.leftNode, visitor);
        visitor.visit(rootNode.element);
        preOrder(rootNode.rightNode, visitor);
    }

    public void postOrder(){
        postOrder(this.rootNode);
    }

    public void postOrderWithStack(){
        postOrderWithStack(this.rootNode);
    }
    // 后序遍历：左 右 根
    private void postOrder(Node<E> rootNode) {
        if (rootNode == null) return;
        postOrder(rootNode.leftNode);
        postOrder(rootNode.rightNode);
        System.out.print(rootNode.element + " ");
    }

    private void postOrderWithStack(Node<E> rootNode){
        if (rootNode == null) return ;
        Stack<Node> stack = new Stack<>();
        Node tempNode = rootNode;
        Node preNode = null;
        while (!stack.isEmpty() || tempNode != null){
            while (tempNode != null){
                stack.push(tempNode);
                tempNode = tempNode.leftNode;
            }
            Node popNode = stack.pop();
            if (popNode.rightNode == null || popNode.rightNode == preNode){
                System.out.print(popNode.element + " ");
                preNode = popNode;
                popNode = null;
            }else {
                stack.push(popNode);
                tempNode = popNode.rightNode;
            }
        }

    }

    public void postOrder(Visitor visitor){
        postOrder(this.rootNode,visitor);
    }
    // 带有遍历方式的后序遍历
    private void postOrder(Node<E> rootNode, Visitor<E> visitor) {
        postOrder(rootNode.leftNode, visitor);
        postOrder(rootNode.rightNode, visitor);
        visitor.visit(rootNode.element);
    }

    public void levelOrder(){
        levelOrder(this.rootNode);
    }

    // 层序遍历
    private void levelOrder(Node<E> rootNode) {
        if (rootNode == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        // 首先根节点入队
        queue.offer(rootNode);
        // 循环检测队中是否存在元素
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.println(node.element);
            // 检查左节点是否存在，存在则入队
            if (node.leftNode != null) {
                queue.offer(node.leftNode);
            }
            // 检查右节点是否存在，存在则入队
            if (node.rightNode != null) {
                queue.offer(node.rightNode);
            }
        }
    }

    // 求二叉树高度
    public int height() {
        return height(this.rootNode);
    }

    // 递归方式求二叉树高度
//    private int height(Node node) {
//        if (node == null) return 0;
//        return Math.max(height(node.leftNode), height(node.rightNode)) + 1;
//    }

    // 层序遍历方式求二叉树高度
    private int height(Node node){
        Queue<Node> queue = new LinkedList();
        queue.offer(node);
        int size = 1;
        int height = 0;
        while(!queue.isEmpty()){
            Node tempNode = queue.poll();
            size = size - 1;
            if (tempNode.leftNode != null){
                queue.offer(tempNode.leftNode);
            }
            if (tempNode.rightNode != null){
                queue.offer(tempNode.rightNode);
            }
            if (size == 0){
                size = queue.size();
                height = height + 1;
            }
        }
        return height;
    }

    // 是否是完全二叉树
    public boolean isComplete(){
        if (rootNode == null) return false;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(rootNode);

        boolean mustBeLeaf = false;

        while (!queue.isEmpty()){
            Node node = queue.poll();
            // 节点必须是叶子结点，但是该节点又不是叶子节点，则不是完全二叉树
            if (mustBeLeaf && (node.rightNode != null || node.leftNode != null)){
                return false;
            }
            // 如果左节点，右节点不为空，则入队
            if (node.leftNode != null) {
                queue.offer(node.leftNode);
            }else if(node.rightNode != null){
                return false;
            }

            if (node.rightNode != null){
                queue.offer(rootNode.rightNode);
            }else {
                mustBeLeaf = false;
            }
        }
        return true;
    }

    // 翻转二叉树
    public Node reverse(){
        return reverse(rootNode);
    }

    /**
     * 递归方式翻转二叉树
     * @param rootNode
     * @return
     */
//    private Node reverse(Node rootNode){
//        if (rootNode == null) return rootNode;
//
//        Node tempNode = rootNode.leftNode;
//        rootNode.leftNode = rootNode.rightNode;
//        rootNode.rightNode = tempNode;
//
//        reverse(rootNode.leftNode);
//        reverse(rootNode.rightNode);
//        return rootNode;
//    }

    /**
     * 层序遍历翻转二叉树
     * @param rootNode
     * @return
     */
    private Node reverse(Node rootNode){
        Queue<Node> queue = new LinkedList<>();
        queue.offer(rootNode);
        while (!queue.isEmpty()){
             Node pullNode = queue.poll();
             // 交换左右节点
             Node tempNode = pullNode.leftNode;
             pullNode.leftNode = pullNode.rightNode;
             pullNode.rightNode = tempNode;
            if (pullNode.rightNode != null){
                queue.offer(pullNode.rightNode);
            }
            if (pullNode.leftNode != null){
                queue.offer(pullNode.leftNode);
            }
        }
        return rootNode;
    }

    // 检查是否为null
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    // 比较e1，e2两个值大小
    private int compare(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable) e1).compareTo(e2);
    }

    @Override
    public Object root() {
        return this.rootNode;
    }

    @Override
    public Object left(Object node) {
        return ((Node)node).leftNode;
    }

    @Override
    public Object right(Object node) {
        return ((Node)node).rightNode;
    }

    @Override
    public Object string(Object node) {
        return ((Node)node).element;
    }

    static class Node<E> {
        E element;
        Node<E> leftNode;
        Node<E> rightNode;
        Node<E> parentNode;
        public Node(E element,Node<E> parentNode) {
            this.element = element;
            this.parentNode = parentNode;
        }
    }

    public interface Visitor<E> {
        void visit(E element);
    }
}
